import javafx.util.Pair;

import java.util.*;

class Node {
    public int val;
    public List<Node> children;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) return ret;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int n = queue.size();
            while (n-- > 0) {
                Node tmp = queue.poll();
                list.add(tmp.val);
                for (Node node : tmp.children) {
                    if (node != null) {
                        queue.add(node);
                    }
                }
            }
            System.out.println();
            ret.add(list);
        }
        return ret;
    }

    //二叉树锯齿形层序遍历
    public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int flag = 1;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            int[] vals = new int[sz];
            int i = 0;
            while (sz-- > 0) {
                TreeNode node = queue.poll();
                vals[i++] = node.val;
                if(node.left!=null) {
                    queue.add(node.left);
                }
                if(node.right!=null) {
                    queue.add(node.right);
                }
            }
            if(flag == -1) {
                reverse(vals);
            }
            flag = -flag;
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j< vals.length; j++) {
                list.add(vals[j]);
            }
            ret.add(list);
        }
        return ret;
    }
    private void reverse(int[] nums) {
        int n = nums.length;
        for(int i =0, j = n-1; i<j; i++,j--) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int flag = 1;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            List<Integer> list = new LinkedList<>();
            while (sz-- > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left!=null) {
                    queue.add(node.left);
                }
                if(node.right!=null) {
                    queue.add(node.right);
                }
            }
            if(flag == -1) {
                Collections.reverse(list);
            }
            flag = -flag;
            ret.add(list);
        }
        return ret;
    }

    //二叉树最大宽度
    public int widthOfBinaryTree(TreeNode root) {
        Queue<Pair<TreeNode,Integer>> queue = new LinkedList<>();
        queue.add(new Pair<TreeNode,Integer>(root,1));
        int ret = 0;
        while(!queue.isEmpty()) {
            List<Pair<TreeNode,Integer>> list = new LinkedList<>();  //存放一层的节点
            int n = queue.size();
            while(n-- > 0) {
                Pair<TreeNode,Integer> pair = queue.poll();
                list.add(pair);
                TreeNode node = pair.getKey();
                int index = pair.getValue();
                if(node.left!=null) {
                    queue.add(new Pair<TreeNode,Integer>(node.left,index*2));
                }
                if(node.right!=null) {
                    queue.add(new Pair<TreeNode,Integer>(node.right,index*2+1));
                }
            }
            Pair<TreeNode,Integer> first = list.get(0);
            Pair<TreeNode,Integer> last = list.get(list.size()-1);
            ret = Math.max(ret,last.getValue()-first.getValue()+1);
        }
        return ret;
    }

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new LinkedList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int flag = 1;
        while (!queue.isEmpty()) {
            int sz = queue.size();
            int m = 0;
            while (sz-- > 0) {
                TreeNode node = queue.poll();
                m = Math.max(m,node.val);
                if(node.left!=null) {
                    queue.add(node.left);
                }
                if(node.right!=null) {
                    queue.add(node.right);
                }
            }
            ret.add(m);
        }
        return ret;
    }
}

